//数组中的最长山脉， 枚举题，来源于leetcode

/**
 * 把符合下列属性的数组 arr 称为 山脉数组 ：

    arr.length >= 3
    存在下标 i（0 < i < arr.length - 1），满足
    arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
    给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/longest-mountain-in-array
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    int longestMountain(vector<int> &arr) {
        //枚举山顶, 时间复杂度n，空间复杂度为n，left和right占用的空间
        vector<int>::size_type n = arr.size();
        if (!n) {
            return 0;
        }
        vector<int> left(n);
        for (int i = 1; i < n; ++i) {
            left[i] = arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0;
        }

        vector<int> right(n);
        for (int i = n - 2; i >= 0; --i) {
            right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 0;
        }

        int res = 0;

        for (int i = 0; i < n; ++i) {
            if (left[i] > 0 && right[i] > 0) {
                res = max(res, left[i] + right[i] + 1);
            }
        }
        return res;
    }

    //从山脚枚举
    int longestMountain2(vector<int> &arr) {
        vector<int>::size_type n = arr.size();
        if (!n) {
            return 0;
        }
        int res = 0, left = 0;

        while (left + 2 < n) {
            int right = left + 1;
            if (arr[left] < arr[right]) {
                while (right + 1 < n && arr[right] < arr[right + 1]) {
                    ++right;
                }
                if (right + 1 < n && arr[right] > arr[right + 1]) {
                    while (right + 1 < n && arr[right] > arr[right + 1]) {
                        ++right;
                    }
                    res = max(res, right - left + 1);
                    left = right + 1;
                } else {
                    ++right;
                }
            }
            left = right;
        }

        return res;
    }
};